﻿#include "stdafx.h"
#include "SearchRotateLists.h"

using namespace std;

namespace algorithm {
int CSearchRotateLists::Search(vector<int>& nums, int target)
{
    int size = (int)nums.size();
    if (size <= 0) {
        return -1;
    }
    else if (size == 1) {
        return target == nums[0] ? 0 : -1;
    }
    int idx = -1;
    for (int i = size - 1; i > 0; i--) {
        if (nums[i - 1] > nums[i]) {
            idx = i;
        }
    }
    if (idx == -1) {
        return BinarySearch(nums, 0, size, target);
    }
    int find = BinarySearch(nums, 0, idx, target);
    return find == -1 ? BinarySearch(nums, idx, size, target) : find;
}

int CSearchRotateLists::BinarySearch(std::vector<int>& nums, int left, int right, int target)
{
    int idx = -1;
    while (left<right) {
        if (right - left <= 1) {
            if (nums[left] == target) {
                idx = left;
            }
            break;
        }
        int mid = (right - left) / 2 + left;
        if (nums[mid] == target) {
            idx = mid;
            break;
        }
        else if(nums[mid]<target){
            left = mid + 1;
        }
        else {
            right = mid;
        }
    }
    return idx;
}
}
